package algorithm.leetcode;

public class 矩形区域不超过K的最大数值和 {
    /*
     * 给定一个非空二维矩阵 matrix 和一个整数 k，找到这个矩阵内部不大于 k 的最大矩形和。
     * 
     * 示例:
     * 
     * 输入: matrix = [[1,0,1],[0,-2,3]], k = 2 输出: 2 解释: 矩形区域 [[0, 1], [-2,
     * 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。
     * 
     * 矩阵内的矩形区域面积必须大于 0。 如果行数远大于列数，你将如何解答呢？
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     */
    public int maxSumSubmatrix(int[][] matrix, int k) {
        /*
         * 执行结果： 通过 显示详情 执行用时 : 362 ms , 在所有 Java 提交中击败了 33.33% 的用户 内存消耗 : 47.2
         * MB , 在所有 Java 提交中击败了 65.52% 的用户 炫耀一下:
         */
        /*
         * 让我们回忆一下，一维的，求连续和不大于k的最大和 计算出sum,然后计算sum[j]-sum[i]
         * 当作是ij区间的和，然后找到不大于k的最大值
         */
        /*
         * 然后看二维如何扩展，先求sum[i][j]的和，然后计算sum[i][j]-sum[m][n],当作是[m][n] 到
         * [i][j]的和，找到不大于k的最大值
         */
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] sum = new int[row + 5][col + 5];
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
        int max = 1 << 31;
        for (int i = 1; i <= row; i++) {
            for (int j = 0; j <= col; j++) {
                for (int m = i; m <= row; m++) {
                    for (int n = j + 1; n <= col; n++) {
                        int area = sum[m][n] - sum[m][j] - sum[i][n] + sum[i][j];
                        if (m == i || n == j) {
                            area = sum[m][n] - sum[i][j];
                        }
                        if (area == k) {
                            return k;
                        }
                        if (area > max && area < k) {
                            max = area;
                        }
                    }
                }
            }
        }
        return max;
    }

    public static void main(String[] args) {
        矩形区域不超过K的最大数值和 run = new 矩形区域不超过K的最大数值和();
        int[][] num = { { 2, 2, -1 } };
        System.err.println(1 << 31);
        System.out.println(run.maxSumSubmatrix(num, 0));
    }
}
